//
//  Problem1030.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/10.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1030. 距离顺序排列矩阵单元格
 给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
 另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
 返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）

 示例 1：
     输入：R = 1, C = 2, r0 = 0, c0 = 0
     输出：[[0,0],[0,1]]
     解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
 示例 2：
     输入：R = 2, C = 2, r0 = 0, c0 = 1
     输出：[[0,1],[0,0],[1,1],[1,0]]
     解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
     [[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
 示例 3：
     输入：R = 2, C = 3, r0 = 1, c0 = 2
     输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
     解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
     其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
 提示：
     1 <= R <= 100
     1 <= C <= 100
     0 <= r0 < R
     0 <= c0 < C
 */
@objcMembers class Problem1030: NSObject {
    func solution() {
        
    }
    
    /*
     暴力破解
     */
    func allCellsDistOrderBao(_ rows: Int, _ cols: Int, _ rCenter: Int, _ cCenter: Int) -> [[Int]] {
        var list:[[Int]] = Array(repeating: [0,0], count: rows*cols)
        for i in 0..<rows {
            for j in 0..<cols {
                list[i * rows + j] = [i,j]
            }
        }
        
        list.sort { fList, sList in
            return (abs(fList[0]-rCenter) + abs(fList[1]-cCenter)) < (abs(sList[0]-rCenter) + abs(sList[1]-cCenter))
        }
        return list
    }
    
    /*
     从（rCenter，cCenter）开始依次执行（-1，0）、（0，1）、（1，0）、（0，-1），只要符合条件的就放入
     */
    func allCellsDistOrder(_ rows: Int, _ cols: Int, _ rCenter: Int, _ cCenter: Int) -> [[Int]] {
        
        var startIndex = 0
        var endIndex = 0
        
        // 存储该位是否已经放到result中
        var stateList = Array(repeating: Array(repeating: 0, count: cols), count: rows)
        
        // 存储按照顺序排列
        var result:[[Int]] = Array(repeating: [0,0], count: rows * cols)
        result[0][0] = rCenter
        result[0][1] = cCenter
        stateList[rCenter][cCenter] = 1
        
        while endIndex < result.count - 1 {
            var nextIndex = endIndex + 1
            for index in (startIndex...endIndex) {
                if result[index][0] - 1 >= 0, stateList[result[index][0] - 1][result[index][1]] == 0 {
                    result[nextIndex][0] = result[index][0] - 1
                    result[nextIndex][1] = result[index][1]
                    stateList[result[nextIndex][0]][result[nextIndex][1]] = 1
                    nextIndex += 1
                }
                if result[index][1] + 1 < cols, stateList[result[index][0]][result[index][1] + 1] == 0 {
                    result[nextIndex][0] = result[index][0]
                    result[nextIndex][1] = result[index][1] + 1
                    stateList[result[nextIndex][0]][result[nextIndex][1]] = 1
                    nextIndex += 1
                }
                if result[index][0] + 1 < rows, stateList[result[index][0] + 1][result[index][1]] == 0 {
                    result[nextIndex][0] = result[index][0] + 1
                    result[nextIndex][1] = result[index][1]
                    stateList[result[nextIndex][0]][result[nextIndex][1]] = 1
                    nextIndex += 1
                }
                if result[index][1] - 1 >= 0, stateList[result[index][0]][result[index][1] - 1] == 0 {
                    result[nextIndex][0] = result[index][0]
                    result[nextIndex][1] = result[index][1] - 1
                    stateList[result[nextIndex][0]][result[nextIndex][1]] = 1
                    nextIndex += 1
                }
            }
            
            startIndex = endIndex + 1
            endIndex = nextIndex - 1
        }
        return result
    }
    
    /*
     依次遍历所有，然后求出距离存放到dic中，然后把dic.key的sort一下
     */
    func allCellsDistOrder2(_ rows: Int, _ cols: Int, _ rCenter: Int, _ cCenter: Int) -> [[Int]] {
        var dic:[Int:[[Int]]] = [:]
        var dist = 0
        for i in (0..<rows) {
            for j in (0..<cols) {
                dist = abs(i - rCenter) + abs(j - cCenter)
                if dic[dist] != nil {
                    dic[dist]?.append([i, j])
                } else {
                    dic[dist] = [[i, j]]
                }
            }
        }
        
        var result: [[Int]] = []
        let keys = dic.keys.sorted()
        for key in keys {
            result.append(contentsOf: dic[key]!)
        }
        
        return result
    }
}
